package tree.searchTree;

import pojo.TreeNode;

/**
 * 功能描述: 二叉搜索树
 *          左子树 < 根节点 < 右子树 每一颗子树都是这样子的才叫搜索二叉树
 * 2024/05/18
 * <p>
 * ZhangYi
 */
public class SearchTreeUtils02 {

    /***
     * 确认左右子树需要返回的信息
     *  1. 是否是搜索二叉树
     *  2. 左子树的最大值
     *  3. 右子树的最小值
     */

    public static class Info{
        private boolean isBST;
        private int max; // 左子树的最大值
        private int min; // 右子树的最小值

        public Info(boolean isBST,
                    int max,
                    int min) {
            this.isBST = isBST;
            this.max = max;
            this.min = min;
        }
    }

    /**
     * 功能描述: 是搜索树
     *
     * @param root
     * @return boolean
     */
    public static  boolean isSearchTree(TreeNode root){
        if (root == null){
            return true;
        }

        return isSearchTreeHelper(root).isBST;
    }

    private static Info isSearchTreeHelper(TreeNode root) {

        if (root == null){
            //return new Info(true, 0, 0);// 这个返回值是有问题的, 如果最大值是负的呢, 如果最小值是负的呢?
            return null;
        }
        int max = root.getId();
        int min =root.getId();

        Info leftInfo = isSearchTreeHelper(root.left);
        Info rightInfo = isSearchTreeHelper(root.right);
        if (leftInfo !=null){
            max = Math.max(leftInfo.max,max);
            min = Math.min(leftInfo.min,min);
        }
        if (rightInfo != null){
            max =Math.max(rightInfo.max,max);
            min =Math.min(rightInfo.min,min);
        }

        boolean isBST = (leftInfo== null ?true: leftInfo.max < root.getId())
                && (rightInfo == null ? true : rightInfo.min > root.getId())
                && (leftInfo == null || leftInfo.isBST)
                && (rightInfo == null || rightInfo.isBST);

        return new Info(isBST,max,min);
    }


    public static void main(String[] args) {
        TreeNode root = generateSearchTree();
        TreeNode root2 = generateNonSearchTree();

        System.out.println(isSearchTree(root));
        System.out.println(isSearchTree(root2));
    }

    /**
     * 功能描述: 生成搜索二叉树
     *
     * @return {@link TreeNode }
     */
    private static TreeNode generateSearchTree() {
        TreeNode treeNode = new TreeNode(23,
                                         "1");
        treeNode.left = new TreeNode(12,
                                     "2");
        treeNode.right = new TreeNode(34,
                                     "3");
        treeNode.left.left = new TreeNode(11,
                                         "4");

        treeNode.left.right = new TreeNode(13,
                                         "5");
        treeNode.right.left = new TreeNode(33,
                                         "6");
        return treeNode;
    }

    /**
     * 功能描述: 生成一颗非搜索二叉树
     *
     * @return {@link TreeNode }
     */
    private static TreeNode generateNonSearchTree() {
        TreeNode treeNode = new TreeNode(23,
                                         "1");
        treeNode.left = new TreeNode(12,
                                     "2");
        treeNode.right = new TreeNode(34,
                                      "3");
        treeNode.left.left = new TreeNode(11,
                                          "4");

        treeNode.left.right = new TreeNode(13,
                                           "5");
        treeNode.right.left = new TreeNode(23,
                                           "6");
        return treeNode;
    }
}
